#define _CRT_SECURE_NO_WARNINGS 2

#include<stdio.h>
#include<stdlib.h>

struct ListNode {
    int data;
    struct ListNode* next;
};

//
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* phead = NULL, * tmp = NULL, * cur = head;
//    while (cur) {
//        if (!phead) {
//            phead = cur;
//            cur = cur->next;
//            phead->next = NULL;
//
//        }
//        else {
//            tmp = cur;
//            cur = cur->next;
//            tmp->next = phead;
//            phead = tmp;
//        }
//
//    }
//    return phead;
//
//}

void SLPrint(struct ListNode* phead) {
    struct ListNode* cur = phead;
    while (cur) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    putchar('\n');
    printf("print successful\n");
}

//struct ListNode* partition(struct ListNode* head, int x) {
//    struct ListNode* head1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* head2 = (struct ListNode*)malloc(sizeof(struct
//        ListNode));
//    struct ListNode* tail1 = head1, * tail2 = head2, * cur = head;
//    tail1->next = NULL, tail2->next = NULL;
//
//    while (cur) {
//        if ((cur->data) < x) {
//            tail1->next = cur;
//            cur = cur->next;
//            tail1 = tail1->next;
//            tail1->next = NULL;
//        }
//        else {
//            tail2->next = cur;
//            cur = cur->next;
//            tail2 = tail2->next;
//            tail2->next = NULL;
//        }
//    }
//    tail1->next = head2;
//    struct ListNode* tmp1 = head1->next;
//    free(head1);
//    head1 = tmp1;
//    struct ListNode* tmp2 = head2->next;
//    free(head2);
//    tail1->next = tmp2;
//    return head1;
//   /* tail1->next = head2;
// 
//    head1 = head1->next;
//    
//    tail1->next = head2->next;
//    return head1;*/
//
//}
struct ListNode* search_mid(struct ListNode* head) {
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

struct ListNode* reverse_mid(struct ListNode* mid) {
    struct ListNode* head = NULL, * cur = mid;
    while (cur) {
        struct ListNode* tmp = cur;
        cur = cur->next;
        tmp->next = head;
        head = tmp;
    }
    return head;
}

int isPalindrome(struct ListNode* head) {
    struct ListNode* phead = head, * mid;
    mid = search_mid(phead);
    struct ListNode* remid = reverse_mid(mid);
    while (remid) {
        if ((remid->data) == (head->data)) {
           remid = remid->next;
            head = head->next;
        }
        else {
            return 0;
        }
    }
    return 1;
}

int main() {
    struct ListNode* newnode1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    newnode1->data = 1;
    struct ListNode* newnode2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    newnode2->data = 2;
    struct ListNode* newnode3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    newnode3->data = 2;
    struct ListNode* newnode4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    newnode4->data = 1;
    /*struct ListNode* newnode5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    newnode5->data = 5;
    struct ListNode* newnode6 = (struct ListNode*)malloc(sizeof(struct ListNode));
    newnode6->data = 6;*/
    newnode1->next = newnode2;
    newnode2->next = newnode3;
    newnode3->next = newnode4;
    newnode4->next = NULL;
    /*newnode4->next = newnode5;
    newnode5->next = newnode6;
    newnode6->next = NULL;*/

   // struct ListNode* ret = partition(newnode1,3);
    //SLPrint(ret);

    int ret = isPalindrome(newnode1);
    return 0;
}